//
//  main.c
//  QuickSort
//
//  Created by DeLong Yang on 2017/8/2.
//  Copyright © 2017年 YiXue. All rights reserved.
//

#include <stdio.h>


/**
 quick sort

 @param a int array
 @param left default first element 出于优化考虑 应当允许外界传入
 @param right max element
 */
void sort(int *a,int left,int right)
{
 
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
         序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
        {
            j--;/*向前寻找*/
        }
        
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
         a[left]，那么就是给key）*/
        
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
         因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
        
        a[j] = a[i];
        printf("%d  -- %d \n",i,j);   // 这里边对于 i == j 的情况  应当结束本次循环
    }
    
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
    /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
    
}


/**
 quick sort 2
 
 @param a int array
 @param left default first element 出于优化考虑 应当允许外界传入
 @param right max element
 */
void sort_2(int *a,int left,int right)
{
    
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
         序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
        {
            j--;/*向前寻找*/
        }
        
        // 加上这句
        if (i == j) {
            continue;
        }
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
         a[left]，那么就是给key）*/
        
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
         因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
        
        // 加上这句
//        if (i == j) {
//            continue;
//        }
        a[j] = a[i];
        printf("%d  -- %d \n",i,j);   // 这里边对于 i == j 的情况  应当结束本次循环
    }
    
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
    /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
    
}

//
void sort_3(int *a,int left,int right)
{
    if (left >= right) {
        return;
    }
    
    int i = left;
    int j = right;
    int k = a[left];
    
    while (i < j) {
        
        while (i<j && k <= a[j]) {  // 升
            j--;
        }
        a[i] = a[j];
        
        while (i<j && k >= a[i]) {
            i++;
        }
        a[j] = a[i];
        
    }
    
    a[i] = k;
    sort_3(a, left, i-1);
    sort_3(a, i+1, right);
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    int a[] = {6,2,7,3,8,9};
    int b[] = {6,2,7,3,8,9};
    int c[] = {9,8,7,6,5,5,4,3,2,1};
    
    sort(a, 0, 5);
    //
    sort_2(b, 0, 5);
    sort_3(c, 0, 10);
    
    printf("the result is \n");
    for (int i =0 ; i<5; i++) {
        printf("%d *** %d \n",a[i],b[i]);
    }
    
    for (int i=0 ; i<10; i++) {
        printf("%d --- \n",c[i]);
    }
    
//    printf("the result is \n");
//    for (int i =0 ; i<5; i++) {
//        printf("%d\n",a[i]);
//    }
    
    return 0;
}
